<!DOCTYPE html>
<html lang="zh-CN">
  <head>
  <meta charset="UTF-8">
  <meta 
    name="viewport"
    content="width=device-width, initial-scale=1.0, minimum-scale=1.0">
  <meta 
    http-equiv="X-UA-Compatible" 
    content="ie=edge">
  <meta 
    name="theme-color" 
    content="#fff" 
    id="theme-color">
  <meta 
    name="description" 
    content="霜序廿的个人网站">
  <link 
    rel="icon" 
    href="https://api2.mubu.com/v3/photo/654b368e-b847-4122-982c-86d90b3f5275.jpg">
  <title>JavaScript中的链表</title>
  
    
      <meta 
        property="og:title" 
        content="JavaScript中的链表">
    
    
      <meta 
        property="og:url" 
        content="https://shuangxunian.github.io/2021/06/13/linkedListsInJavaScript/index.html">
    
    
      <meta 
        property="og:img" 
        content="https://api2.mubu.com/v3/photo/654b368e-b847-4122-982c-86d90b3f5275.jpg">
    
    
      <meta 
        property="og:img" 
        content="如题目">
    
    
      <meta 
        property="og:type" 
        content="article">
      <meta 
        property="og:article:published_time" 
        content="2021-06-13">
      <meta 
        property="og:article:modified_time" 
        content="2021-01-28">
      <meta 
        property="og:article:author" 
        content="霜序廿">
      
        
          <meta 
            property="og:article:tag" 
            content="js">
        
          <meta 
            property="og:article:tag" 
            content="算法">
        
      
    
  
  <script>
    function loadScript(url, cb) {
      var script = document.createElement('script');
      script.src = url;
      if (cb) script.onload = cb;
      script.async = true;
      document.body.appendChild(script);
    }
    function loadCSS(href, data, attr) {
      var sheet = document.createElement('link');
      sheet.ref = 'stylesheet';
      sheet.href = href;
      sheet.dataset[data] = attr;
      document.head.appendChild(sheet);
    }
    function changeCSS(cssFile, data, attr) {
      var oldlink = document.querySelector(data);
      var newlink = document.createElement("link");
      newlink.setAttribute("rel", "stylesheet");
      newlink.setAttribute("href", cssFile);
      newlink.dataset.prism = attr;
      document.head.replaceChild(newlink, oldlink);
    }
  </script>
  
    
      
      
      
      
        
        
        
        <script>
          function prismThemeChange() {
            if(document.getElementById('theme-color').dataset.mode === 'dark') {
              if(document.querySelector('[data-prism]')) {
                changeCSS('/js/lib/prism/prism-tomorrow.min.css', '[data-prism]', 'prism-tomorrow');
              } else {
                loadCSS('/js/lib/prism/prism-tomorrow.min.css', 'prism', 'prism-tomorrow');
              }
            } else {
              if(document.querySelector('[data-prism]')) {
                changeCSS('/js/lib/prism/prism.min.css', '[data-prism]', 'prism');
              } else {
                loadCSS('/js/lib/prism/prism.min.css', 'prism', 'prism');
              }
            }
          }
          prismThemeChange()
        </script>
      
      
        
        <link rel="stylesheet" href="/js/lib/prism/prism-line-numbers.min.css">
      
    
  
  <script>
    // control reverse button
    var reverseDarkList = {
      dark: 'light',
      light: 'dark'
    };
    var themeColor = {
      dark: '#1c1c1e',
      light: '#fff'
    }
    // get the data of css prefers-color-scheme
    var getCssMediaQuery = function() {
      return window.matchMedia('(prefers-color-scheme: dark)').matches ? 'dark' : 'light';
    };
    // reverse current darkmode setting function
    var reverseDarkModeSetting = function() {
      var setting = localStorage.getItem('user-color-scheme');
      if(reverseDarkList[setting]) {
        setting = reverseDarkList[setting];
      } else if(setting === null) {
        setting = reverseDarkList[getCssMediaQuery()];
      } else {
        return;
      }
      localStorage.setItem('user-color-scheme', setting);
      return setting;
    };
    // apply current darkmode setting
  </script>
  
    <script>
      var setDarkmode = function(mode) {
      var setting = mode || localStorage.getItem('user-color-scheme');
      if(setting === getCssMediaQuery()) {
        document.documentElement.removeAttribute('data-user-color-scheme');
        localStorage.removeItem('user-color-scheme');
        document.getElementById('theme-color').content = themeColor[setting];
        document.getElementById('theme-color').dataset.mode = setting;
        prismThemeChange();
      } else if(reverseDarkList[setting]) {
        document.documentElement.setAttribute('data-user-color-scheme', setting);
        document.getElementById('theme-color').content = themeColor[setting];
        document.getElementById('theme-color').dataset.mode = setting;
        prismThemeChange();
      } else {
        document.documentElement.removeAttribute('data-user-color-scheme');
        localStorage.removeItem('user-color-scheme');
        document.getElementById('theme-color').content = themeColor[getCssMediaQuery()];
        document.getElementById('theme-color').dataset.mode = getCssMediaQuery();
        prismThemeChange();
      }
    };
    setDarkmode();
    </script>
  
  
  <link rel="preload" href="//at.alicdn.com/t/font_1946621_i1kgafibvw.css" as="style" >
  <link rel="preload" href="//at.alicdn.com/t/font_1952792_89b4ac4k4up.css" as="style" >
  
  
    <link rel="preload" href="/js/lib/lightbox/baguetteBox.min.js" as="script">
    <link rel="preload" href="/js/lib/lightbox/baguetteBox.min.css" as="style" >
  
  
    <link rel="preload" href="/js/lib/lozad.min.js" as="script">
  
  
  
  
  
  
  
  <link rel="stylesheet" href="/css/main.css">
  
  <link rel="stylesheet" href="//at.alicdn.com/t/font_1946621_i1kgafibvw.css">
  
  <link rel="stylesheet" href="//at.alicdn.com/t/font_1952792_89b4ac4k4up.css">
  
    <link rel="stylesheet" href="/js/lib/lightbox/baguetteBox.min.css">
  
<meta name="generator" content="Hexo 5.4.0"></head>

  <body>
    <div class="wrapper">
       
      <nav class="navbar">
  <div class="navbar-logo">
    <span class="navbar-logo-main">
      
        <img 
          class="navbar-logo-img" 
          src="https://api2.mubu.com/v3/photo/654b368e-b847-4122-982c-86d90b3f5275.jpg" 
          alt="blog logo">
      
      <span class="navbar-logo-dsc">霜序廿的个人网站</span>
    </span>
  </div>
  <div class="navbar-menu">
    
      <a 
        href="/" 
        class="navbar-menu-item">
        
          首页
        
      </a>
    
      <a 
        href="/archives" 
        class="navbar-menu-item">
        
          归档
        
      </a>
    
      <a 
        href="/tags" 
        class="navbar-menu-item">
        
          标签
        
      </a>
    
      <a 
        href="/categories" 
        class="navbar-menu-item">
        
          分类
        
      </a>
    
      <a 
        href="/about" 
        class="navbar-menu-item">
        
          关于
        
      </a>
    
      <a 
        href="/links" 
        class="navbar-menu-item">
        
          友链
        
      </a>
    
    <a 
      class="navbar-menu-item darknavbar" 
      id="dark">
      <i class="iconfont icon-weather"></i>
    </a>
    <a 
      class="navbar-menu-item searchnavbar" 
      id="search">
      <i 
        class="iconfont icon-search" 
        style="font-size: 1.2rem; font-weight: 400;">
      </i>
    </a>
  </div>
</nav> 
      
      <div 
        id="local-search" 
        style="display: none">
        <input
          class="navbar-menu-item"
          id="search-input"
          placeholder="请输入搜索内容..." />
        <div id="search-content"></div>
      </div>
      
      <div class="section-wrap">
        <div class="container">
          <div class="columns">
            <main class="main-column">
<article class="card card-content">
  <header>
    <h1 class="post-title">
      JavaScript中的链表
    </h1>
  </header>
  <div class="post-meta post-show-meta">
    <time datetime="2021-06-13T13:48:56.178Z">
      <i 
        class="iconfont icon-calendar" 
        style="margin-right: 2px;">
      </i>
      <span>2021-06-13</span>
    </time>
    
      <span class="dot"></span>
      
        <a 
          href="/categories/%E6%8A%80%E6%9C%AF%E6%96%87%E7%AB%A0/" 
          class="post-meta-link">
          技术文章
        </a>
      
    
    
      <span class="dot"></span>
      <span>6.6k 字</span>
    
  </div>
  
    <div 
      class="post-meta post-show-meta" 
      style="margin-top: -10px;">
      <div style="display: flex; align-items: center;">
        <i 
          class="iconfont icon-biaoqian" 
          style="margin-right: 2px; font-size: 1.15rem;">
        </i>
        
          
          <a 
            href="/tags/js/" 
            class="post-meta-link">
            js
          </a>
        
          
            <span class="dot"></span>
          
          <a 
            href="/tags/%E7%AE%97%E6%B3%95/" 
            class="post-meta-link">
            算法
          </a>
        
      </div>
    </div>
  
  </header>
  <div 
    id="section" 
    class="post-content">
    <h2 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h2><p>此文会先探讨下什么是链表以及在 JavaScript 中的链表，接着我们会使用 JavaScript 这门语言动手实现下各类链表的设计，最后我们会抛出一些常规疑问，并从各个方面一一解答，总之，目的就是完全搞定链表</p>
<h2 id="什么是链表"><a href="#什么是链表" class="headerlink" title="什么是链表"></a>什么是链表</h2><p>通常我们在程序中想要存储多个元素，数组可能是最常用的数据结构，数组这种数据结构非常方便，它甚至可以通过非常简单的方式即 [] 这种语法来访问其元素</p>
<p>而链表存储的也是有序的元素集合，但不同于数组的是，链表中的元素在内存中并不是连续的，每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也可以称为指针）组成</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/81bbbccd-d060-462a-9da0-b66f2b9af2b1-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/81bbbccd-d060-462a-9da0-b66f2b9af2b1-3807603.jpg"></p>
<p>我们接着再来看数组这种数据结构，它有一个缺点，在大多数语言中数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素，如下图</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/7152ec0e-3503-4977-951f-cf679f07e4cb-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/7152ec0e-3503-4977-951f-cf679f07e4cb-3807603.jpg"></p>
<p>上图数组删除索引为 2 值为 3 的元素，那么我们首先要删掉 3 这个元素，因为索引为 2 值为 3 的元素删除了，索引 2 就空了，所以接着，我们要把索引 3 也就是元素 4 向前移动一位，与此同时后面的元素 5 也需要向前移动一位，向数组中插入一个元素也是这个道理，只要数组中少了一位或者多了一位，那么后面的元素都要依次向前或向后移动一位，那么可想而之，当数组长度很大的时候，插入及删除的效率就会逐渐降低</p>
<p>我们再来看看链表</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/30d86a17-ad47-4075-80d6-cd92b42c4b2f-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/30d86a17-ad47-4075-80d6-cd92b42c4b2f-3807603.jpg"></p>
<p>同样是删除元素 3，链表这里只需要迭代到值为 3 的节点，将节点 2 指向节点 4 就行了，节点 3 没有了引用关系，就会被垃圾回收机制当作垃圾回收了，即使当节点非常多的情况下，依然只用改变一下引用关系即可删除元素，而插入元素则是反过来，即先断开插入位置两边的元素，然后让前一个元素指向插入元素，插入元素指向后一个元素即可，元素越多对比数组的效率就会越高</p>
<p>相对于传统的数组，链表的一个好处就在于，添加或移除元素的时候不需要移动其他元素，但是在数组中，我们可以直接访问任何位置的任何元素，链表中是不行的，因为链表中每个节点只有对下一个节点的引用，所以想访问链表中间的一个元素，必须要从起点（链表头部节点）开始迭代链表直到找到所需的元素，这点需要注意</p>
<h2 id="JavaScript中的链表"><a href="#JavaScript中的链表" class="headerlink" title="JavaScript中的链表"></a>JavaScript中的链表</h2><p>上面我们简单介绍了常规链表的概念，但是在 JavaScript 这门语言中，我们怎么表示链表呢？</p>
<p>由于 JS 中没有内置链表这种数据结构，所以我们需要使用对象来模拟实现链表，就如同我们上面介绍链表，它其实是一个单向链表，除此之外还有双向链表、环形链表等等，我们接下来会一一介绍并使用 JavaScript 来实现下</p>
<h3 id="单向链表"><a href="#单向链表" class="headerlink" title="单向链表"></a>单向链表</h3><p>我们先来看基础的单项链表，单向链表每个元素由一个存储元素本身的节点和一个指向下一个元素的指针构成，如下图</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/e9014e78-858b-4539-b1e3-ee610e82d524-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/e9014e78-858b-4539-b1e3-ee610e82d524-3807603.jpg"></p>
<p>要实现链表这种数据结构，关键在于保存 head 元素（即链表的头元素）以及每一个元素的 next 指针，有这两部分我们就可以很方便地遍历链表从而操作所有的元素，你可以把链表想象成一条铁链，铁链中的每一个节点都是相互连接的，我们只要找到铁链的头，整条铁链就都可以找到了，那么单向链表在 JS 中究竟要如何来模拟呢，我们一步一步来</p>
<p>首先，我们要创建一个类，这个类的作用就是描述链表的节点，它很简单，只需要有两个属性就可以了，一个用来保存此节点的值，一个用来保存指向下一个节点的指针，如下</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">/**
 * @description: 创建链表单节点类
 * @param &#123;*&#125; val 节点值
 * @return &#123;*&#125;
 */</span>
<span class="token keyword">function</span> <span class="token function">ListNode</span><span class="token punctuation">(</span><span class="token parameter">val</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>val <span class="token operator">=</span> val
  <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>接着，我们需要先写一个链表类，其中 length属性 代表链表长度，head属性 代表链表头部节点</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">/**
 * @description: 创建链表类
 * @param &#123;*&#125;
 * @return &#123;*&#125;
 */</span>
<span class="token keyword">function</span> <span class="token function">LinkedList</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>length <span class="token operator">=</span> <span class="token number">0</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>head <span class="token operator">=</span> <span class="token keyword">null</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<p>我们思考下，既然是来模拟一个链表类，那么就应该把它所有可能会用到的特性都塞进这个类里，就比如数组有 push/splice/indexOf/… 等等这些好用的方法我们链表必须也得有啊，我们先仔细构思下要给链表添加哪些实用的特性或者说方法，先搭一个基础骨架，这里我列出了很多，我们来一一实现下，也欢迎补充</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 向链表中追加节点</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">append</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">val</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token punctuation">&#125;</span>

<span class="token comment">// 在链表的指定位置插入节点</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">insert</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">index<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token punctuation">&#125;</span>

<span class="token comment">// 删除链表中指定位置的元素，并返回这个元素的值</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">removeAt</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">index</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token punctuation">&#125;</span>

<span class="token comment">// 删除链表中对应的元素</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">remove</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">val</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token punctuation">&#125;</span>

<span class="token comment">// 获取链表中给定元素的索引</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">indexOf</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">val</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token punctuation">&#125;</span>

<span class="token comment">// 获取链表中某个节点</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">find</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">val</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token punctuation">&#125;</span>

<span class="token comment">// 获取链表中索引所对应的元素</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">getElementAt</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">index</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token punctuation">&#125;</span>

<span class="token comment">// 判断链表是否为空</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">isEmpty</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token punctuation">&#125;</span>

<span class="token comment">// 获取链表的长度</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">size</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token punctuation">&#125;</span>

<span class="token comment">// 获取链表的头元素</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">getHead</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token punctuation">&#125;</span>

<span class="token comment">// 清空链表</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">clear</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token punctuation">&#125;</span>

<span class="token comment">// 序列化链表</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">join</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">string</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="getElementAt-index"><a href="#getElementAt-index" class="headerlink" title="getElementAt(index)"></a>getElementAt(index)</h4><p>我们先来实现获取链表中索引所对应的元素即 getElementAt 方法以及通过节点值获取链表元素即 find 方法，因为后面要多次用到它们，我们先说 getElementAt 方法，上面我们说想要找一个元素，我们必须从头迭代，所以我们直接根据传入的索引进行迭代即可</p>
<p>首先判断参数 index 的边界值，如果值超出了索引的范围（小于 0 或者大于 length - 1），则返回null，我们从链表的 head 节点开始，遍历整个链表直到找到对应索引位置的节点，然后返回这个节点，是不是很简单？和所有有序数据集合一样，链表的索引也是从 0 开始，只要有链表的头节点，就可以遍历找到索引所在位置的元素，所以我们在构造函数即 LinkedList 类中保存了 head 值</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 获取链表中索引所对应的元素</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">getElementAt</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">index</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">>=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token keyword">null</span>

  <span class="token keyword">let</span> cur <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>head
  <span class="token keyword">while</span> <span class="token punctuation">(</span>index<span class="token operator">--</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    cur <span class="token operator">=</span> cur<span class="token punctuation">.</span>next
  <span class="token punctuation">&#125;</span>
  <span class="token keyword">return</span> cur
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="find-val"><a href="#find-val" class="headerlink" title="find(val)"></a>find(val)</h4><p>find 方法和 getElementAt 方法类似，一个通过索引找元素，一个通过节点值找元素，所以我们直接迭代查找对比即可</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 获取链表中某个节点</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">find</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">val</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">let</span> cur <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>head
  <span class="token keyword">while</span> <span class="token punctuation">(</span>cur<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>cur<span class="token punctuation">.</span>val <span class="token operator">==</span> val<span class="token punctuation">)</span> <span class="token keyword">return</span> cur
    cur <span class="token operator">=</span> cur<span class="token punctuation">.</span>next
  <span class="token punctuation">&#125;</span>
  <span class="token keyword">return</span> <span class="token keyword">null</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="append-val"><a href="#append-val" class="headerlink" title="append(val)"></a>append(val)</h4><p>有了 getElementAt 方法后，接下来我们就可以很方便地实现 append 方法，此方法的作用是在链表末尾追加元素</p>
<p>此方法传入的是一个值，我们可以通过上面的构造函数 ListNode 来创建一个新节点</p>
<p>而后，我们需要考虑，如果链表的 head 为 null 时，这种情况表示链表为空，所以需要将 head 节点指向新添加的元素，以此来确保存储头节点，如果不为空，我们通过 getElementAt 方法找到链表的最后一个节点，最后一个节点的索引就是构造函数中的我们存的链表长度 length 属性减去 1，再将最后一个节点的 next 指针指向新添加的元素即可</p>
<p>新添加的元素 next 指针默认为 null，链表最后一个元素的 next 值也就为 null，另外，将节点挂到链表上之后，还需将链表的长度加 1，保证 length 属性等于链表长度，如下</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 向链表中追加节点</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">append</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">val</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span>val<span class="token punctuation">)</span>

  <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span><span class="token keyword">this</span><span class="token punctuation">.</span>head<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>head <span class="token operator">=</span> node
  <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">let</span> cur <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getElementAt</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span>
    cur<span class="token punctuation">.</span>next <span class="token operator">=</span> node
  <span class="token punctuation">&#125;</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>length<span class="token operator">++</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="insert-index-val"><a href="#insert-index-val" class="headerlink" title="insert(index, val)"></a>insert(index, val)</h4><p>接下来我们要实现 insert 方法，即在链表的任意位置添加节点</p>
<p>在指定位置插入元素，首先我们还是需要先判断下传入 index 索引是否超出边界</p>
<p>接着我们分两种情况考虑</p>
<p>当 index 的值为 0 时，表示要在链表的头部插入新节点，将新插入节点的 next 指针指向现在的 head，然后更新 head 的值为新插入的节点即可，如下图</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/2bdd11c3-b22a-49de-8eec-89e99f8d4f39-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/2bdd11c3-b22a-49de-8eec-89e99f8d4f39-3807603.jpg"></p>
<p>当 index 的值不为 0 时，即插入的节点在链表的中间或者尾部，我们首先找到待插入位置的前一个节点 prevNode，然后将新节点 newNode 的 next 指针指向 prevNode 的 next 所对应的节点，再将 prevNode 的 next 指针指向 newNode，这样就把新节点插入链表中了，当插入的节点在链表的尾部，这种方法也同样适用，如下图</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/14942c6a-80f1-4da0-97f1-2908fa44705e-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/14942c6a-80f1-4da0-97f1-2908fa44705e-3807603.jpg"></p>
<p>最后，我们插入了节点，还需要将链表的长度即 length 长度加 1，代码如下</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 在链表的指定位置插入节点</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">insert</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">index<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">></span> <span class="token keyword">this</span><span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">false</span>

  <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span>val<span class="token punctuation">)</span>

  <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">===</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    node<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>head
    <span class="token keyword">this</span><span class="token punctuation">.</span>head <span class="token operator">=</span> node
  <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">let</span> prev <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getElementAt</span><span class="token punctuation">(</span>index <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span>
    node<span class="token punctuation">.</span>next <span class="token operator">=</span> prev<span class="token punctuation">.</span>next
    prev<span class="token punctuation">.</span>next <span class="token operator">=</span> node
  <span class="token punctuation">&#125;</span>

  <span class="token keyword">this</span><span class="token punctuation">.</span>length<span class="token operator">++</span>
  <span class="token keyword">return</span> <span class="token boolean">true</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="removeAt-index"><a href="#removeAt-index" class="headerlink" title="removeAt(index)"></a>removeAt(index)</h4><p>相同的方式，我们可以很容易地写出 removeAt 方法，用来删除链表中指定位置的节点</p>
<p>依然还是先判断下传入 index 索引是否超出边界</p>
<p>还是分两种情况</p>
<p>如果要删除的节点是链表的头部，将 head 移到下一个节点即可，如果当前链表只有一个节点，那么下一个节点为 null，此时将 head 指向下一个节点等同于将 head 设置成 null，删除之后链表为空</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/84135b39-c470-4f2c-b5aa-2141c6bf4c1f-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/84135b39-c470-4f2c-b5aa-2141c6bf4c1f-3807603.jpg"></p>
<p>如果要删除的节点在链表的中间部分，我们需要找出 index 所在位置的前一个节点，将它的 next 指针指向 index 所在位置的下一个节点，总之，删除节点只需要修改相应节点的指针，断开删除位置左右相邻的节点再重新连接上即可</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/03942cd9-ec43-4d3c-9c1e-6b2add5bf1e2-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/03942cd9-ec43-4d3c-9c1e-6b2add5bf1e2-3807603.jpg"></p>
<p>被删除的节点没有了引用关系，JavaScript 垃圾回收机制会处理它，关于垃圾回收机制，同样不在此文讨论范围内，知道即可，删除节点元素，我们还需将链表的长度减 1，最终代码如下</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 删除链表中指定位置的元素，并返回这个元素的值</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">removeAt</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">index</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">>=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token keyword">null</span>

  <span class="token keyword">let</span> cur <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>head

  <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">===</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>head <span class="token operator">=</span> cur<span class="token punctuation">.</span>next
  <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">let</span> prev <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getElementAt</span><span class="token punctuation">(</span>index <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span>
    cur <span class="token operator">=</span> prev<span class="token punctuation">.</span>next
    prev<span class="token punctuation">.</span>next <span class="token operator">=</span> cur<span class="token punctuation">.</span>next
  <span class="token punctuation">&#125;</span>

  <span class="token keyword">this</span><span class="token punctuation">.</span>length<span class="token operator">--</span>
  <span class="token keyword">return</span> cur<span class="token punctuation">.</span>val
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="indexOf-val"><a href="#indexOf-val" class="headerlink" title="indexOf(val)"></a>indexOf(val)</h4><p>获取链表中给定元素的索引，这个比较简单，直接迭代即可，匹配到了返回对应索引，匹配不到返回 -1</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 获取链表中给定元素的索引</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">indexOf</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">val</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">let</span> cur <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>head

  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token keyword">this</span><span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>cur<span class="token punctuation">.</span>val <span class="token operator">===</span> val<span class="token punctuation">)</span> <span class="token keyword">return</span> i
    cur <span class="token operator">=</span> cur<span class="token punctuation">.</span>next
  <span class="token punctuation">&#125;</span>

  <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="remove-val"><a href="#remove-val" class="headerlink" title="remove(val)"></a>remove(val)</h4><p>删除链表中对应的元素，有了之前的铺垫，这里就比较简单了，我们可以直接用 indexOf 方法拿到对应索引，再使用 removeAt 方法删除节点即可</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 删除链表中对应的元素</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">remove</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">val</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">let</span> index <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">indexOf</span><span class="token punctuation">(</span>val<span class="token punctuation">)</span>
  <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">removeAt</span><span class="token punctuation">(</span>index<span class="token punctuation">)</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="isEmpty"><a href="#isEmpty" class="headerlink" title="isEmpty()"></a>isEmpty()</h4><p>判断链表是否为空，只需要我们判断一下链表长度 length 等不等于 0 即可</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 判断链表是否为空</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">isEmpty</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">return</span> <span class="token operator">!</span><span class="token keyword">this</span><span class="token punctuation">.</span>length
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="size"><a href="#size" class="headerlink" title="size()"></a>size()</h4><p>获取链表长度就是取其 length</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 获取链表的长度</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">size</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>length
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="getHead"><a href="#getHead" class="headerlink" title="getHead()"></a>getHead()</h4><p>获取链表的头元素即返回 head 属性即可</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 获取链表的头元素</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">getHead</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>head
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="clear"><a href="#clear" class="headerlink" title="clear()"></a>clear()</h4><p>清空链表，我们只需要将 head 置空，然后让 length 等于 0，等待垃圾回收机制回收无引用的废弃链表即可</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 清空链表</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">clear</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>head <span class="token operator">=</span> <span class="token keyword">null</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>length <span class="token operator">=</span> <span class="token number">0</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="join-string"><a href="#join-string" class="headerlink" title="join(string)"></a>join(string)</h4><p>序列化链表即使用指定格式输出链表，类似于数组中 join 方法，此举旨在便于我们测试</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 序列化链表</span>
<span class="token class-name">LinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">join</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">string</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">let</span> cur <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>head
  <span class="token keyword">let</span> str <span class="token operator">=</span> <span class="token string">''</span>
  <span class="token keyword">while</span> <span class="token punctuation">(</span>cur<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    str <span class="token operator">+=</span> cur<span class="token punctuation">.</span>val

    <span class="token keyword">if</span> <span class="token punctuation">(</span>cur<span class="token punctuation">.</span>next<span class="token punctuation">)</span> str <span class="token operator">+=</span> string

    cur <span class="token operator">=</span> cur<span class="token punctuation">.</span>next
  <span class="token punctuation">&#125;</span>
  <span class="token keyword">return</span> str
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>那么到此，我们的单向链表类就设计完成了。</p>
<h3 id="双向链表"><a href="#双向链表" class="headerlink" title="双向链表"></a>双向链表</h3><p>上面我们说了单向链表，接下来我们来说双向链表，那么什么是双向链表呢？其实听名字就可以听出来，单向链表中每一个元素只有一个 next 指针，用来指向下一个节点，我们只能从链表的头部开始遍历整个链表，任何一个节点只能找到它的下一个节点，而不能找到它的上一个节点，双向链表中的每一个元素拥有两个指针，一个用来指向下一个节点，一个用来指向上一个节点，双向链表中，除了可以像单向链表一样从头部开始遍历之外，还可以从尾部进行遍历，如下图</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/5336f6b6-cf8f-45e2-830d-7fd73efedba1-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/5336f6b6-cf8f-45e2-830d-7fd73efedba1-3807603.jpg"></p>
<p>同单向链表，我们首先创建链表节点类，不同的是，它需要多一个 prev 属性用来指向前一个节点</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">/**
 * @description: 创建双向链表单节点类
 * @param &#123;*&#125; val 节点值
 * @return &#123;*&#125;
 */</span>
<span class="token keyword">function</span> <span class="token function">ListNode</span><span class="token punctuation">(</span><span class="token parameter">val</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>val <span class="token operator">=</span> val
  <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>prev <span class="token operator">=</span> <span class="token keyword">null</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>双向链表类同单向链表多增加了一个尾部节点 tail</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">/**
 * @description: 创建双向链表类
 * @param &#123;*&#125;
 * @return &#123;*&#125;
 */</span>
<span class="token keyword">function</span> <span class="token function">DoubleLinkedList</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>length <span class="token operator">=</span> <span class="token number">0</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>head <span class="token operator">=</span> <span class="token keyword">null</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>tail <span class="token operator">=</span> <span class="token keyword">null</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>接下来我们来实现双向链表的原型方法</p>
<h4 id="getElementAt-index-1"><a href="#getElementAt-index-1" class="headerlink" title="getElementAt(index)"></a>getElementAt(index)</h4><p>首先就是，获取双向链表中索引所对应的元素，双向链表由于可以双向进行迭代查找，所以这里 getElementAt 方法我们可以进行优化，当索引大于链表长度 length/2 时，我们可以从后往前找，反之则从前向后找，这样可以更快找到该节点元素</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 获取双向链表中索引所对应的元素</span>
<span class="token class-name">DoubleLinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">getElementAt</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">index</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">>=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token keyword">null</span>
 
  <span class="token keyword">let</span> cur <span class="token operator">=</span> <span class="token keyword">null</span>
  <span class="token keyword">if</span><span class="token punctuation">(</span>index <span class="token operator">></span> Math<span class="token punctuation">.</span><span class="token function">floor</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>length <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token comment">// 从后往前</span>
    cur <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>tail
    <span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>i <span class="token operator">></span> index<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
      cur <span class="token operator">=</span> cur<span class="token punctuation">.</span>prev
      i<span class="token operator">--</span>
    <span class="token punctuation">&#125;</span>
  <span class="token punctuation">&#125;</span><span class="token keyword">else</span><span class="token punctuation">&#123;</span>
    <span class="token comment">// 从前往后</span>
    cur <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>head
    <span class="token keyword">while</span> <span class="token punctuation">(</span>index<span class="token operator">--</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
      cur <span class="token operator">=</span> cur<span class="token punctuation">.</span>next
    <span class="token punctuation">&#125;</span>
  <span class="token punctuation">&#125;</span>
  <span class="token keyword">return</span> cur
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="find-val-1"><a href="#find-val-1" class="headerlink" title="find(val)"></a>find(val)</h4><p>find 方法和 getElementAt 方法是类似的，getElementAt 方法可以优化，那么 find 再变成双向链表后也可优化，我们想，既然双向都可以进行迭代，那么我们两边同时迭代岂不是更快，双向迭代的情况下，只有找不到时才会迭代整个链表，效率更高</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 获取双向链表中某个节点</span>
<span class="token class-name">DoubleLinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">find</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">val</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
 <span class="token keyword">let</span> curHead <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>head
  <span class="token keyword">let</span> curTail <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>tail
  <span class="token keyword">while</span> <span class="token punctuation">(</span>curHead<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>curHead<span class="token punctuation">.</span>val <span class="token operator">==</span> val<span class="token punctuation">)</span> <span class="token keyword">return</span> curHead
    curHead <span class="token operator">=</span> curHead<span class="token punctuation">.</span>next

    <span class="token keyword">if</span> <span class="token punctuation">(</span>curTail<span class="token punctuation">.</span>val <span class="token operator">==</span> val<span class="token punctuation">)</span> <span class="token keyword">return</span> curTail
    curTail <span class="token operator">=</span> curTail<span class="token punctuation">.</span>prev
  <span class="token punctuation">&#125;</span>
  <span class="token keyword">return</span> <span class="token keyword">null</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="append-val-1"><a href="#append-val-1" class="headerlink" title="append(val)"></a>append(val)</h4><p>又来到了我们的追加节点元素，双向链表追加与单向链表还是有些区别的</p>
<p>当链表为空时，除了要将 head 指向当前添加的节点外，还要将 tail 也指向当前要添加的节点</p>
<p>当链表不为空时，直接将 tail 的 next 指向当前要添加的节点 node，然后修改 node 的 prev 指向旧的 tail，最后修改 tail 为新添加的节点</p>
<p>双向链表的追加操作我们不需要从头开始遍历整个链表，通过 tail 可以直接找到链表的尾部，这一点比单向链表的操作更方便，最后将 length 值加 1，修改链表的长度即可</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 向双向链表中追加节点</span>
<span class="token class-name">DoubleLinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">append</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">val</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span>val<span class="token punctuation">)</span>

  <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>head <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token comment">// 链表为空，head 和 tail 都指向当前添加的节点</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>head <span class="token operator">=</span> node
    <span class="token keyword">this</span><span class="token punctuation">.</span>tail <span class="token operator">=</span> node
  <span class="token punctuation">&#125;</span>
  <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
    <span class="token comment">// 链表不为空，将当前节点添加到链表的尾部</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>tail<span class="token punctuation">.</span>next <span class="token operator">=</span> node
    node<span class="token punctuation">.</span>prev <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>tail
    <span class="token keyword">this</span><span class="token punctuation">.</span>tail <span class="token operator">=</span> node
  <span class="token punctuation">&#125;</span>

  <span class="token keyword">this</span><span class="token punctuation">.</span>length<span class="token operator">++</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="insert-index-val-1"><a href="#insert-index-val-1" class="headerlink" title="insert(index, val)"></a>insert(index, val)</h4><p>接着是插入节点元素方法，同样思路一致，并不困难，我们注意 tail 及 prev 指针分情况讨论，插入后长度加 1 即可</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 在双向链表的指定位置插入节点</span>
<span class="token class-name">DoubleLinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">insert</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">index<span class="token punctuation">,</span> val</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">></span> <span class="token keyword">this</span><span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">false</span>

  <span class="token comment">// 插入到尾部</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">===</span> <span class="token keyword">this</span><span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">append</span><span class="token punctuation">(</span>val<span class="token punctuation">)</span>
  <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span>val<span class="token punctuation">)</span>

    <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">===</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token comment">// 插入到头部</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>head <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>head <span class="token operator">=</span> node
        <span class="token keyword">this</span><span class="token punctuation">.</span>tail <span class="token operator">=</span> node
      <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
        node<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>head
        <span class="token keyword">this</span><span class="token punctuation">.</span>head<span class="token punctuation">.</span>prev <span class="token operator">=</span> node
        <span class="token keyword">this</span><span class="token punctuation">.</span>head <span class="token operator">=</span> node
      <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span> <span class="token comment">// 插入到中间位置</span>
      <span class="token keyword">let</span> curNode <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getElementAt</span><span class="token punctuation">(</span>index<span class="token punctuation">)</span>
      <span class="token keyword">let</span> prevNode <span class="token operator">=</span> curNode<span class="token punctuation">.</span>prev
      node<span class="token punctuation">.</span>next <span class="token operator">=</span> curNode
      node<span class="token punctuation">.</span>prev <span class="token operator">=</span> prevNode
      prevNode<span class="token punctuation">.</span>next <span class="token operator">=</span> node
      curNode<span class="token punctuation">.</span>prev <span class="token operator">=</span> node
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>length<span class="token operator">++</span>
  <span class="token punctuation">&#125;</span>
  <span class="token keyword">return</span> <span class="token boolean">true</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="removeAt-index-1"><a href="#removeAt-index-1" class="headerlink" title="removeAt(index)"></a>removeAt(index)</h4><p>删除双向链表中指定位置的元素，同样是注意 tail 及 prev 指针分情况讨论，最后删除后长度减 1 即可</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 删除双向链表中指定位置的元素，并返回这个元素的值</span>
<span class="token class-name">DoubleLinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">removeAt</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">index</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">>=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token keyword">null</span>

  <span class="token keyword">let</span> current <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>head
  <span class="token keyword">let</span> prevNode

  <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">===</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token comment">// 移除头部元素</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>head <span class="token operator">=</span> current<span class="token punctuation">.</span>next
    <span class="token keyword">this</span><span class="token punctuation">.</span>head<span class="token punctuation">.</span>prev <span class="token operator">=</span> <span class="token keyword">null</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>length <span class="token operator">===</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">this</span><span class="token punctuation">.</span>tail <span class="token operator">=</span> <span class="token keyword">null</span>
  <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">===</span> <span class="token keyword">this</span><span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token comment">// 移除尾部元素</span>
    current <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>tail
    <span class="token keyword">this</span><span class="token punctuation">.</span>tail <span class="token operator">=</span> current<span class="token punctuation">.</span>prev
    <span class="token keyword">this</span><span class="token punctuation">.</span>tail<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span>
  <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span> <span class="token comment">// 移除中间元素</span>
    current <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getElementAt</span><span class="token punctuation">(</span>index<span class="token punctuation">)</span>
    prevNode <span class="token operator">=</span> current<span class="token punctuation">.</span>prev
    prevNode<span class="token punctuation">.</span>next <span class="token operator">=</span> current<span class="token punctuation">.</span>next
    current<span class="token punctuation">.</span>next<span class="token punctuation">.</span>prev <span class="token operator">=</span> prevNode
  <span class="token punctuation">&#125;</span>

  <span class="token keyword">this</span><span class="token punctuation">.</span>length<span class="token operator">--</span>
  <span class="token keyword">return</span> current<span class="token punctuation">.</span>val
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="indexOf-val-1"><a href="#indexOf-val-1" class="headerlink" title="indexOf(val)"></a>indexOf(val)</h4><p>在双向链表中查找元素索引，有了上面的 find 方法做铺垫，这里就简单了，思路一致，</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 获取双向链表中给定元素的索引</span>
<span class="token class-name">DoubleLinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">indexOf</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">val</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">let</span> curHead <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>head
  <span class="token keyword">let</span> curTail <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>tail
  <span class="token keyword">let</span> idx <span class="token operator">=</span> <span class="token number">0</span>
  <span class="token keyword">while</span> <span class="token punctuation">(</span>curHead <span class="token operator">!==</span> curTail<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>curHead<span class="token punctuation">.</span>val <span class="token operator">==</span> val<span class="token punctuation">)</span> <span class="token keyword">return</span> idx
    curHead <span class="token operator">=</span> curHead<span class="token punctuation">.</span>next

    <span class="token keyword">if</span> <span class="token punctuation">(</span>curTail<span class="token punctuation">.</span>val <span class="token operator">==</span> val<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span> <span class="token operator">-</span> idx
    curTail <span class="token operator">=</span> curTail<span class="token punctuation">.</span>prev

    idx<span class="token operator">++</span>
  <span class="token punctuation">&#125;</span>
  <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h4 id="join-string-1"><a href="#join-string-1" class="headerlink" title="join(string)"></a>join(string)</h4><p>序列化链表我们还是和上面单向链表一致即可</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token comment">// 序列化双向链表</span>
<span class="token class-name">DoubleLinkedList</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">join</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">string</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  <span class="token keyword">let</span> cur <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>head
  <span class="token keyword">let</span> str <span class="token operator">=</span> <span class="token string">''</span>
  <span class="token keyword">while</span> <span class="token punctuation">(</span>cur<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
    str <span class="token operator">+=</span> cur<span class="token punctuation">.</span>val

    <span class="token keyword">if</span> <span class="token punctuation">(</span>cur<span class="token punctuation">.</span>next<span class="token punctuation">)</span> str <span class="token operator">+=</span> string

    cur <span class="token operator">=</span> cur<span class="token punctuation">.</span>next
  <span class="token punctuation">&#125;</span>
  <span class="token keyword">return</span> str
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h3 id="环形链表"><a href="#环形链表" class="headerlink" title="环形链表"></a>环形链表</h3><p>我们再来看另一种链表，环形链表，顾名思义，环形链表的尾部节点指向它自己的头节点</p>
<p>环形链表有单向环形链表，也可以有双向环形链表，如下图</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/b035b339-8da9-41fa-b4e0-140dc5ea6b37-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/b035b339-8da9-41fa-b4e0-140dc5ea6b37-3807603.jpg"></p>
<p>单双环形链表这里我们就不再一一的写了，对比上面我们环形链表只需要注意下尾部节点要指向头节点即可</p>
<h2 id="为什么JavaScript中不内置链表？"><a href="#为什么JavaScript中不内置链表？" class="headerlink" title="为什么JavaScript中不内置链表？"></a>为什么JavaScript中不内置链表？</h2><p>根据我们上面所说，链表有这么多优点，那么为什么 JavaScript 这门语言不内置链表这种数据结构呢？</p>
<p>其实 JS 中，数组几乎实现了链表的所有功能，所以没那个必要去再麻烦一次了，听到这里你可能会疑惑，上面不是说，数组在某些情况（例如头部插入等等）下性能不如链表吗？</p>
<p>我们来用事实说话，现在我们用上面完成的单向链表类 LinkedList，同原生数组做一个简单的的时间测试</p>
<pre class="line-numbers language-javascript" data-language="javascript"><code class="language-javascript"><span class="token keyword">let</span> linkedList <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">LinkedList</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token keyword">let</span> arr <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>

<span class="token comment">// 测试 分别尝试 「总数100 插入节点50」/「总数100000 插入节点50000」</span>
<span class="token keyword">let</span> count <span class="token operator">=</span> <span class="token number">100</span>
<span class="token keyword">let</span> insertIndex <span class="token operator">=</span> <span class="token number">50</span>
<span class="token comment">// let count = 100000</span>
<span class="token comment">// let insertIndex = 50000</span>

console<span class="token punctuation">.</span><span class="token function">time</span><span class="token punctuation">(</span><span class="token string">'链表push操作'</span><span class="token punctuation">)</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> count<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  linkedList<span class="token punctuation">.</span><span class="token function">append</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span>
<span class="token punctuation">&#125;</span>
console<span class="token punctuation">.</span><span class="token function">timeEnd</span><span class="token punctuation">(</span><span class="token string">'链表push操作'</span><span class="token punctuation">)</span>

console<span class="token punctuation">.</span><span class="token function">time</span><span class="token punctuation">(</span><span class="token string">'数组push操作'</span><span class="token punctuation">)</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> count<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
  arr<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span>
<span class="token punctuation">&#125;</span>
console<span class="token punctuation">.</span><span class="token function">timeEnd</span><span class="token punctuation">(</span><span class="token string">'数组push操作'</span><span class="token punctuation">)</span>


console<span class="token punctuation">.</span><span class="token function">time</span><span class="token punctuation">(</span><span class="token string">'链表insert操作'</span><span class="token punctuation">)</span>
linkedList<span class="token punctuation">.</span><span class="token function">insert</span><span class="token punctuation">(</span><span class="token string">'test节点'</span><span class="token punctuation">,</span> insertIndex<span class="token punctuation">)</span>
console<span class="token punctuation">.</span><span class="token function">timeEnd</span><span class="token punctuation">(</span><span class="token string">'链表insert操作'</span><span class="token punctuation">)</span>

console<span class="token punctuation">.</span><span class="token function">time</span><span class="token punctuation">(</span><span class="token string">'数组insert操作'</span><span class="token punctuation">)</span>
arr<span class="token punctuation">.</span><span class="token function">splice</span><span class="token punctuation">(</span>insertIndex<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token string">'test节点'</span><span class="token punctuation">)</span>
console<span class="token punctuation">.</span><span class="token function">timeEnd</span><span class="token punctuation">(</span><span class="token string">'数组insert操作'</span><span class="token punctuation">)</span>


console<span class="token punctuation">.</span><span class="token function">time</span><span class="token punctuation">(</span><span class="token string">'链表remove操作'</span><span class="token punctuation">)</span>
linkedList<span class="token punctuation">.</span><span class="token function">removeAt</span><span class="token punctuation">(</span>insertIndex<span class="token punctuation">)</span>
console<span class="token punctuation">.</span><span class="token function">timeEnd</span><span class="token punctuation">(</span><span class="token string">'链表remove操作'</span><span class="token punctuation">)</span>

console<span class="token punctuation">.</span><span class="token function">time</span><span class="token punctuation">(</span><span class="token string">'数组remove操作'</span><span class="token punctuation">)</span>
arr<span class="token punctuation">.</span><span class="token function">splice</span><span class="token punctuation">(</span>insertIndex<span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span>
console<span class="token punctuation">.</span><span class="token function">timeEnd</span><span class="token punctuation">(</span><span class="token string">'数组remove操作'</span><span class="token punctuation">)</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>我们来看下结果</p>
<p>追加 100 个数据，在索引 50 插入元素，再删除插入的元素</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/6294dca7-ce2a-4312-a35a-5a0737edd527-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/6294dca7-ce2a-4312-a35a-5a0737edd527-3807603.jpg"></p>
<p>追加 100000 个数据，在索引 50000 插入元素，再删除插入的元素</p>
<p><img  srcset="data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20300%20300'%3E%3C/svg%3E" data-src="https://api2.mubu.com/v3/document_image/176a5d95-82c8-4ccd-91eb-7c85b4052ad7-3807603.jpg" class="lozad post-image"src="https://api2.mubu.com/v3/document_image/176a5d95-82c8-4ccd-91eb-7c85b4052ad7-3807603.jpg"></p>
<p>我们从测试结果可以看到不论基数为 100 这样的小量级或者基数为 100000 这样一个很大的量级时，原生 Array 的性能都依然碾压链表</p>
<p>也就是说链表效率高于数组效率这种话，事实上在 JS 中是不存在的，即使你创建一个长度为 1 亿的数组，再创建一个长度为 10 的数组，并且向这两个数组的中间添加元素，console.time 时间出来看看，你会发现所用时间与数组长度长度无关，这说明 JS 数组达到了链表的效率要求</p>
<p>而且数组中我们也可以用 splice() 方法向数组的指定位置去添加和删除元素，经测试，所需时间同样与数组长度无关，也能达到链表的要求，而数组的下标完全可以取代链表的 head,tail,next,prev 等方法，并且大多数情况下会更方便些，再加上工作中链表这种数据结构的使用场景不是太多，所以可以说 JS 中的数组是完爆链表的</p>
<p>当然，这只局限于 JavaScript 这门语言中，这和 JS 内部的数组实现机制有关，其实 JS 中的数组只是叫数组而已，它和常规语言中的数组概念就不同，那么关于数组概念以及内部实现，不在我们此章节讨论范围之内，先留一个疑问，过几天有空了再另起一篇 JS 数组相关的文章吧，其实自己找去答案最好了，我们说 JS 是一门解释型高级语言，它的底层实现并不像我们看起来那么简单循规，有点打破常规的意思</p>
<h2 id="JavaScript中链表无用？"><a href="#JavaScript中链表无用？" class="headerlink" title="JavaScript中链表无用？"></a>JavaScript中链表无用？</h2><p>如我们上面所说，难道 JavaScript 中的链表当真就毫无作用了吗？</p>
<p>其实也不是，就比如三大法宝之一 React 中的 Fiber 架构，就用到了链表这种数据结构</p>
<p>Fiber 在英文中的意思为 纤维化，即细化，将任务进行细化，它把一个耗时长的任务分成很多小片，每一个小片的运行时间很短，虽然总时间依然很长，但是在每个小片执行完之后，都给其他任务一个执行的机会，这样唯一的线程就不会被独占，其他任务依然有运行的机会，React 中的 Fiber 就把整个 VDOM 的更新过程碎片化</p>
<p>在之前 React 中的 render() 方法会接收一个 虚拟DOM 对象和一个真实的 容器DOM 作为 虚拟DOM 渲染完成后的挂载节点，其主要作用就是将 虚拟DOM 渲染为 真实DOM 并挂载到容器下，这个方法在更新的时候是进行递归操作的，如果在更新的过程中有大量的节点需要更新，就会出现长时间占用 JS 主线程的情况，并且整个递归过程是无法被打断的，由于 JS 线程和 GUI 线程是互斥的，所以大量更新的情况下你可能会看到界面有些卡顿</p>
<p>Fiber 架构其实就解决两个问题，一是保证任务在浏览器空闲的时候执行，二是将任务进行碎片化，接下来我们简单说下 Fiber</p>
<p>JS 中有一个实验性质的方法 requestIdleCallback(callback) ，它可以传入一个回调函数，回调函数能够收到一个 deadline 对象，通过该对象的 timeRemaining() 方法可以获取到当前浏览器的空闲时间，如果有空闲时间，那么就可以执行一小段任务，如果时间不足了，则继续 requestIdleCallback，等到浏览器又有空闲时间的时候再接着执行，这样就实现了浏览器空闲的时候执行</p>
<p>但是 虚拟DOM 是树结构，当任务被打断后，树结构无法恢复之前的任务继续执行，所以需要一种新的数据结构，也就是我们的链表，链表可以包含多个指针，Fiber 采用的链表中就包含三个指针，parent 指向其父 Fiber  节点，child 指向其子 Fiber 节点，sibling 指向其兄弟 Fiber 节点，一个 Fiber 节点对应一个任务节点，这样就可以轻易找到下一个节点，继而也就可以恢复任务的执行</p>
<p>这简简单单的一段，就是大名鼎鼎的 Fiber 架构，那么你说链表有用吗？</p>
<p>说了这么多，其实对于普通需求，我们 JS 确实不需要用到链表，数组能完爆它，但是特殊需求里，链表独具它一定的优势，总之三个字，看需求，再者，我们现在是在用 JS 来阐述链表，但是其它常规语言可没有 JS 中的数组这么强悍，而且学会了链表，我们下一个学习树结构时就更加得心应手了</p>
<h2 id="参考链接"><a href="#参考链接" class="headerlink" title="参考链接"></a>参考链接</h2><p><a target="_blank" rel="noopener" href="https://mp.weixin.qq.com/s/fQh_qWXMJDZcs7L9teBamg">「算法与数据结构」JavaScript中的链表</a></p>

  </div>
  <div>
    
  </div>
</article>
<div class="nav">
  
    <div class="nav-item-prev">
      <a 
        href="/2021/06/13/longListsInFrontEndDevelopment/" 
        class="nav-link">
        <i class="iconfont icon-left nav-prev-icon"></i>
        <div>
          <div class="nav-label">上一篇</div>
          
            <div class="nav-title">聊聊前端开发中的长列表 </div>
          
        </div>
      </a>
    </div>
  
  
    <div class="nav-item-next">
      <a 
        href="/2021/06/13/Let&#39;sTalkAboutTheImplementationOfTheFrontEndVirtualList/" 
        class="nav-link">
        <div>
          <div class="nav-label">下一篇</div>
          
            <div class="nav-title">再谈前端虚拟列表的实现 </div>
          
        </div>
        <i class="iconfont icon-right nav-next-icon"></i>
      </a>
    </div>
  
</div>

<div 
  class="card card-content toc-card" 
  id="mobiletoc">
  <div class="toc-header">
  <i 
    class="iconfont icon-menu" 
    style="padding-right: 2px;">
  </i>目录
</div>
<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%89%8D%E8%A8%80"><span class="toc-text">前言</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BB%80%E4%B9%88%E6%98%AF%E9%93%BE%E8%A1%A8"><span class="toc-text">什么是链表</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#JavaScript%E4%B8%AD%E7%9A%84%E9%93%BE%E8%A1%A8"><span class="toc-text">JavaScript中的链表</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8D%95%E5%90%91%E9%93%BE%E8%A1%A8"><span class="toc-text">单向链表</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#getElementAt-index"><span class="toc-text">getElementAt(index)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#find-val"><span class="toc-text">find(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#append-val"><span class="toc-text">append(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#insert-index-val"><span class="toc-text">insert(index, val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#removeAt-index"><span class="toc-text">removeAt(index)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#indexOf-val"><span class="toc-text">indexOf(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#remove-val"><span class="toc-text">remove(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#isEmpty"><span class="toc-text">isEmpty()</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#size"><span class="toc-text">size()</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#getHead"><span class="toc-text">getHead()</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#clear"><span class="toc-text">clear()</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#join-string"><span class="toc-text">join(string)</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8"><span class="toc-text">双向链表</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#getElementAt-index-1"><span class="toc-text">getElementAt(index)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#find-val-1"><span class="toc-text">find(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#append-val-1"><span class="toc-text">append(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#insert-index-val-1"><span class="toc-text">insert(index, val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#removeAt-index-1"><span class="toc-text">removeAt(index)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#indexOf-val-1"><span class="toc-text">indexOf(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#join-string-1"><span class="toc-text">join(string)</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8"><span class="toc-text">环形链表</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88JavaScript%E4%B8%AD%E4%B8%8D%E5%86%85%E7%BD%AE%E9%93%BE%E8%A1%A8%EF%BC%9F"><span class="toc-text">为什么JavaScript中不内置链表？</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#JavaScript%E4%B8%AD%E9%93%BE%E8%A1%A8%E6%97%A0%E7%94%A8%EF%BC%9F"><span class="toc-text">JavaScript中链表无用？</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E9%93%BE%E6%8E%A5"><span class="toc-text">参考链接</span></a></li></ol>
</div></main>
            <aside class="left-column">
              
              <div class="card card-author">
                
  <img 
    src="https://api2.mubu.com/v3/photo/654b368e-b847-4122-982c-86d90b3f5275.jpg" 
    class="author-img" 
    alt="author avatar">

<p class="author-name">霜序廿</p>
<p class="author-description">无限进步</p>
<div class="author-message">
  <a 
    class="author-posts-count" 
    href="/archives">
    <span>253</span>
    <span>文章</span>
  </a>
  <a 
    class="author-categories-count" 
    href="/categories">
    <span>6</span>
    <span>分类</span>
  </a>
  <a 
    class="author-tags-count" 
    href="/tags">
    <span>51</span>
    <span>标签</span>
  </a>
</div>

  <div class="author-card-society">
    
      <div class="author-card-society-icon">
        <a target="_blank" rel="noopener" href="https://github.com/shuangxunian">
          <i class="iconfont icon-github society-icon"></i>
        </a>
      </div>
    
      <div class="author-card-society-icon">
        <a target="_blank" rel="noopener" href="https://space.bilibili.com/391117803">
          <i class="iconfont icon-bilibili society-icon"></i>
        </a>
      </div>
    
  </div>

              </div>
               <div class="sticky-tablet">
  
  
    <article class="display-when-two-columns spacer">
      <div class="card card-content toc-card">
        <div class="toc-header">
  <i 
    class="iconfont icon-menu" 
    style="padding-right: 2px;">
  </i>目录
</div>
<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%89%8D%E8%A8%80"><span class="toc-text">前言</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BB%80%E4%B9%88%E6%98%AF%E9%93%BE%E8%A1%A8"><span class="toc-text">什么是链表</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#JavaScript%E4%B8%AD%E7%9A%84%E9%93%BE%E8%A1%A8"><span class="toc-text">JavaScript中的链表</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8D%95%E5%90%91%E9%93%BE%E8%A1%A8"><span class="toc-text">单向链表</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#getElementAt-index"><span class="toc-text">getElementAt(index)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#find-val"><span class="toc-text">find(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#append-val"><span class="toc-text">append(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#insert-index-val"><span class="toc-text">insert(index, val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#removeAt-index"><span class="toc-text">removeAt(index)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#indexOf-val"><span class="toc-text">indexOf(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#remove-val"><span class="toc-text">remove(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#isEmpty"><span class="toc-text">isEmpty()</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#size"><span class="toc-text">size()</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#getHead"><span class="toc-text">getHead()</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#clear"><span class="toc-text">clear()</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#join-string"><span class="toc-text">join(string)</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8"><span class="toc-text">双向链表</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#getElementAt-index-1"><span class="toc-text">getElementAt(index)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#find-val-1"><span class="toc-text">find(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#append-val-1"><span class="toc-text">append(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#insert-index-val-1"><span class="toc-text">insert(index, val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#removeAt-index-1"><span class="toc-text">removeAt(index)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#indexOf-val-1"><span class="toc-text">indexOf(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#join-string-1"><span class="toc-text">join(string)</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8"><span class="toc-text">环形链表</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88JavaScript%E4%B8%AD%E4%B8%8D%E5%86%85%E7%BD%AE%E9%93%BE%E8%A1%A8%EF%BC%9F"><span class="toc-text">为什么JavaScript中不内置链表？</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#JavaScript%E4%B8%AD%E9%93%BE%E8%A1%A8%E6%97%A0%E7%94%A8%EF%BC%9F"><span class="toc-text">JavaScript中链表无用？</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E9%93%BE%E6%8E%A5"><span class="toc-text">参考链接</span></a></li></ol>
      </div>
    </article>
  
  
  <article class="card card-content categories-widget">
    <div class="categories-card">
  <div class="categories-header">
    <i 
      class="iconfont icon-fenlei" 
      style="padding-right: 2px;">
    </i>分类
  </div>
  <div class="categories-list">
    
      <a href="/categories/%E6%8A%80%E6%9C%AF%E6%96%87%E7%AB%A0/">
        <div class="categories-list-item">
          技术文章
          <span class="categories-list-item-badge">218</span>
        </div>
      </a>
    
      <a href="/categories/%E5%85%B6%E4%BB%96/">
        <div class="categories-list-item">
          其他
          <span class="categories-list-item-badge">16</span>
        </div>
      </a>
    
      <a href="/categories/%E6%97%85%E6%B8%B8/">
        <div class="categories-list-item">
          旅游
          <span class="categories-list-item-badge">1</span>
        </div>
      </a>
    
      <a href="/categories/%E7%AE%97%E6%B3%95/">
        <div class="categories-list-item">
          算法
          <span class="categories-list-item-badge">8</span>
        </div>
      </a>
    
      <a href="/categories/%E8%80%83%E8%AF%95/">
        <div class="categories-list-item">
          考试
          <span class="categories-list-item-badge">8</span>
        </div>
      </a>
    
      <a href="/categories/%E9%98%85%E8%AF%BB/">
        <div class="categories-list-item">
          阅读
          <span class="categories-list-item-badge">1</span>
        </div>
      </a>
    
  </div>
</div>
  </article>
  
  <article class="card card-content tags-widget">
    <div class="tags-card">
  <div class="tags-header">
    <i 
      class="iconfont icon-biaoqian" 
      style="padding-right: 2px;">
    </i>热门标签
  </div>
  <div class="tags-list">
    
      <a 
        href="/tags/js/" 
        title="js">
        <div class="tags-list-item">js</div>
      </a>
    
      <a 
        href="/tags/vue/" 
        title="vue">
        <div class="tags-list-item">vue</div>
      </a>
    
      <a 
        href="/tags/%E9%9D%A2%E8%AF%95/" 
        title="面试">
        <div class="tags-list-item">面试</div>
      </a>
    
      <a 
        href="/tags/css/" 
        title="css">
        <div class="tags-list-item">css</div>
      </a>
    
      <a 
        href="/tags/%E7%BD%91%E7%BB%9C/" 
        title="网络">
        <div class="tags-list-item">网络</div>
      </a>
    
      <a 
        href="/tags/%E5%85%B6%E4%BB%96/" 
        title="其他">
        <div class="tags-list-item">其他</div>
      </a>
    
      <a 
        href="/tags/%E7%AE%97%E6%B3%95/" 
        title="算法">
        <div class="tags-list-item">算法</div>
      </a>
    
      <a 
        href="/tags/%E6%B5%8F%E8%A7%88%E5%99%A8/" 
        title="浏览器">
        <div class="tags-list-item">浏览器</div>
      </a>
    
      <a 
        href="/tags/html/" 
        title="html">
        <div class="tags-list-item">html</div>
      </a>
    
      <a 
        href="/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" 
        title="操作系统">
        <div class="tags-list-item">操作系统</div>
      </a>
    
      <a 
        href="/tags/%E8%80%83%E8%AF%95/" 
        title="考试">
        <div class="tags-list-item">考试</div>
      </a>
    
      <a 
        href="/tags/%E8%BD%AF%E5%AE%9E%E5%8A%9B/" 
        title="软实力">
        <div class="tags-list-item">软实力</div>
      </a>
    
      <a 
        href="/tags/DOM/" 
        title="DOM">
        <div class="tags-list-item">DOM</div>
      </a>
    
      <a 
        href="/tags/%E8%BD%AE%E5%AD%90/" 
        title="轮子">
        <div class="tags-list-item">轮子</div>
      </a>
    
      <a 
        href="/tags/%E7%BD%91%E7%BB%9C%E5%8E%9F%E7%90%86/" 
        title="网络原理">
        <div class="tags-list-item">网络原理</div>
      </a>
    
      <a 
        href="/tags/debug/" 
        title="debug">
        <div class="tags-list-item">debug</div>
      </a>
    
  </div>
</div>
  </article>
  
  
</div>
            </aside>
            <aside class="right-column">
              <div class="sticky-widescreen">
  
  
    <article class="card card-content toc-card">
      <div class="toc-header">
  <i 
    class="iconfont icon-menu" 
    style="padding-right: 2px;">
  </i>目录
</div>
<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%89%8D%E8%A8%80"><span class="toc-text">前言</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BB%80%E4%B9%88%E6%98%AF%E9%93%BE%E8%A1%A8"><span class="toc-text">什么是链表</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#JavaScript%E4%B8%AD%E7%9A%84%E9%93%BE%E8%A1%A8"><span class="toc-text">JavaScript中的链表</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8D%95%E5%90%91%E9%93%BE%E8%A1%A8"><span class="toc-text">单向链表</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#getElementAt-index"><span class="toc-text">getElementAt(index)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#find-val"><span class="toc-text">find(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#append-val"><span class="toc-text">append(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#insert-index-val"><span class="toc-text">insert(index, val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#removeAt-index"><span class="toc-text">removeAt(index)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#indexOf-val"><span class="toc-text">indexOf(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#remove-val"><span class="toc-text">remove(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#isEmpty"><span class="toc-text">isEmpty()</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#size"><span class="toc-text">size()</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#getHead"><span class="toc-text">getHead()</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#clear"><span class="toc-text">clear()</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#join-string"><span class="toc-text">join(string)</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8"><span class="toc-text">双向链表</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#getElementAt-index-1"><span class="toc-text">getElementAt(index)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#find-val-1"><span class="toc-text">find(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#append-val-1"><span class="toc-text">append(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#insert-index-val-1"><span class="toc-text">insert(index, val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#removeAt-index-1"><span class="toc-text">removeAt(index)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#indexOf-val-1"><span class="toc-text">indexOf(val)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#join-string-1"><span class="toc-text">join(string)</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8"><span class="toc-text">环形链表</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88JavaScript%E4%B8%AD%E4%B8%8D%E5%86%85%E7%BD%AE%E9%93%BE%E8%A1%A8%EF%BC%9F"><span class="toc-text">为什么JavaScript中不内置链表？</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#JavaScript%E4%B8%AD%E9%93%BE%E8%A1%A8%E6%97%A0%E7%94%A8%EF%BC%9F"><span class="toc-text">JavaScript中链表无用？</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E9%93%BE%E6%8E%A5"><span class="toc-text">参考链接</span></a></li></ol>
    </article>
  
  
  <article class="card card-content">
    <div class="recent-posts-card">
  <div class="recent-posts-header">
    <i 
      class="iconfont icon-wenzhang_huaban" 
      style="padding-right: 2px;">
    </i>最近文章
  </div>
  <div class="recent-posts-list">
    
      <div class="recent-posts-item">
        <div class="recent-posts-item-title">2022-05-01</div>
        <a href="/2022/05/01/typescriptHome/"><div class="recent-posts-item-content">typescript</div></a>
      </div>
    
      <div class="recent-posts-item">
        <div class="recent-posts-item-title">2022-01-15</div>
        <a href="/2022/01/15/javaScriptTheVariousWaysAndAdvantagesAndDisadvantagesOfDeepInheritance/"><div class="recent-posts-item-content">JavaScript深入之继承的多种方式和优缺点</div></a>
      </div>
    
      <div class="recent-posts-item">
        <div class="recent-posts-item-title">2022-01-15</div>
        <a href="/2022/01/15/javaScriptGoFromPrototypeToPrototypeChain/"><div class="recent-posts-item-content">JavaScript深入之从原型到原型链</div></a>
      </div>
    
      <div class="recent-posts-item">
        <div class="recent-posts-item-title">2022-01-15</div>
        <a href="/2022/01/15/javaScriptMemoryLeakTutorial/"><div class="recent-posts-item-content">JavaScript 内存泄漏教程</div></a>
      </div>
    
  </div>
</div>
  </article>
  
  
  
  <article class="card card-content">
    <div class="recent-posts-card">
  <div class="recent-posts-header">
    关注嘉然！顿顿解馋！
  </div>
  <div class="recent-posts-list">
    
      <img 
        src="https://api2.mubu.com/v3/document_image/2697c6ae-10ee-41a3-9099-304bdb252d31-3807603.jpg" 
        class="myadd-img" 
        alt="author avatar">
    
  </div>
</div>
  </article>
</div>
            </aside>
          </div>
        </div>
      </div>
    </div>
     
    <footer class="footer">
  <div class="footer-container">
    <div>
      <div class="footer-dsc">
        <span>
          Copyright ©
          
            2020 -
          
          2022
        </span>
        &nbsp;
        <a 
          href="/" 
          class="footer-link">
          霜序廿的个人网站
        </a>
      </div>
    </div>

    
      <div class="footer-dsc">
        
          Powered by
          <a 
            href="https://hexo.io/" 
            class="footer-link" 
            target="_blank" 
            rel="nofollow noopener noreferrer">
            &nbsp;Hexo
          </a>
        
        
          <span>&nbsp;|&nbsp;</span>
        
        
          Theme -
          <a 
            href="https://github.com/theme-kaze" 
            class="footer-link" 
            target="_blank"
            rel="nofollow noopener noreferrer">
            &nbsp;Kaze
          </a>
        
      </div>
    
    
    
    
</footer> 
    
  <a 
    role="button" 
    id="scrollbutton" 
    class="basebutton" 
    aria-label="回到顶部">
    <i class="iconfont icon-arrowleft button-icon"></i>
  </a>

<a 
  role="button" 
  id="menubutton" 
  class="basebutton">
  <i class="iconfont icon-menu button-icon"></i>
</a>
<a 
  role="button" 
  id="popbutton" 
  class="basebutton" 
  aria-label="控制中心">
  <i class="iconfont icon-expand button-icon"></i>
</a>
<a 
  role="button" 
  id="darkbutton" 
  class="basebutton darkwidget" 
  aria-label="夜色模式">
  <i class="iconfont icon-weather button-icon"></i>
</a>
<a 
  role="button" 
  id="searchbutton" 
  class="basebutton searchwidget" 
  aria-label="搜索">
  <i class="iconfont icon-search button-icon"></i>
</a> 
     
     
     
      <script>
  var addImgLayout = function () {
    var img = document.querySelectorAll('.post-content img')
    var i
    for (i = 0; i < img.length; i++) {
      var wrapper = document.createElement('a')
      wrapper.setAttribute('href', img[i].getAttribute('data-src'))
      wrapper.setAttribute('aria-label', 'illustration')
      wrapper.style.cssText =
        'width: 100%; display: flex; justify-content: center;'
      if (img[i].alt) wrapper.dataset.caption = img[i].alt
      wrapper.dataset.nolink = true
      img[i].before(wrapper)
      wrapper.append(img[i])
      var divWrap = document.createElement('div')
      divWrap.classList.add('gallery')
      wrapper.before(divWrap)
      divWrap.append(wrapper)
    }
    baguetteBox.run('.gallery')
  }
</script>
<script>
  loadScript(
    "/js/lib/lightbox/baguetteBox.min.js",
    addImgLayout
  )
</script>
 
     
     
    <script src="/js/main.js"></script> 
     
    
      <script>
        var addLazyload = function () {
          var observer = lozad('.lozad', {
            load: function (el) {
              el.srcset = el.getAttribute('data-src')
            },
            loaded: function (el) {
              el.classList.add('loaded')
            },
          })
          observer.observe()
        }
      </script>
      <script>
        loadScript('/js/lib/lozad.min.js', addLazyload)
      </script>
     
    
    
  </body>
</html>
